
package tsp;

import java.util.ArrayList;

public class TSP_Calcul {

    private TSP_Data tsp_data;

    public TSP_Calcul(TSP_Data tsp_dat){
        tsp_data = tsp_dat;
    }

    public int[] calculerAffectations(ArrayList<Integer> cycle) {

        int[] affectation = new int[tsp_data.getNbSommets()];

        /* Affecter les sommets restants aux sommets du cycle généré */
        for (int i = 0; i < tsp_data.getNbSommets(); i++) {
            //Pour chaque sommet hors cycle, trouver le sommet du cycle
            //le plus proche
            if (horsCycle(i,cycle)) {
                affectation[i] = trouverPlusProcheSommet(i,cycle);
            } else {
                affectation[i] = -1;
            }
        }
        return affectation;
    }

    /**
     * Teste si un sommet donné n'appartient pas au cycle de la solution
     * @param s le sommet à tester
     * @param cycle le cycle considéré
     * @return vrai si le sommet est hors cycle (affecté, false sinon
     */
    public boolean horsCycle(int s, ArrayList<Integer> cycle) {
        return !cycle.contains(s);
    }

    /**
     * Pour un sommet hors cycle donné s, trouve le sommet du cycle le plus proche
     * auquel s doit être affecté
     * @param s le sommet testé
     * @param cycle le cycle considéré
     * @return le sommet le plus proche de s ou -1 si aucun sommet dans le cycle
     */
    private int trouverPlusProcheSommet(int s, ArrayList<Integer> cycle) {
        int plusProche = -1;
        double coutAffectation = Double.MAX_VALUE;

        double[][] coutsAffectation = tsp_data.getCoutsAffectation();

        //s ne doit pas être un sommet du cycle évidemment...
        if (cycle.contains(s)) {
            return -1;
        }

        //Tester tous les sommets du cycle
        for (int sommetCycle : cycle) {
            //Si on trouve plus proche que le sommet précédent
            if (coutsAffectation[s][sommetCycle] < coutAffectation) {
                plusProche = sommetCycle;
                coutAffectation = coutsAffectation[s][sommetCycle];
            }
        }

        return plusProche;
    }

    /**
     * Trouve le sommet successeur d'un sommet donné
     * @param s le sommet à partir duquel on recherche le suivant
     * @param cycle le cycle considéré
     * @return le successeur de s
     */
    private int trouverSommetSuivant(int s, ArrayList<Integer> cycle) {
        //Si le soommet est le dernier élément du cycle, alors le suivant
        //est le premier élément de la liste
        if (cycle.indexOf(s) == cycle.size() - 1) {
            return cycle.get(0);
        } else {
            return cycle.get(cycle.indexOf(s) + 1);
        }
    }

    /**
     * Calcule le cout total de la solution (cycle + affectations)
     * @param cycle le cycle considéré
     * @param affectation le tableau est sommets affectés aux sommets du cycle
     * @return le cout de la solution
     */
    public int calculerCoutSolution(ArrayList<Integer> cycle, int[] affectation) {
        int coutCycle = 0;
        int coutAffectations = 0;
        int coutSolution;
        double[][] coutsCycle = tsp_data.getCoutsCycle();
        double[][] coutsAffectation = tsp_data.getCoutsAffectation();

        /* 1- Calcul de la somme des couts des arcs du cycle */
        int sommetCycle, sommetCycleSuivant;

        for (int i = 0; i < cycle.size(); i++) {
            sommetCycle = cycle.get(i);

            //Si on a atteint le bout de la liste c'est que le suivant
            //est le sommet initial du cycle
            sommetCycleSuivant = trouverSommetSuivant(sommetCycle, cycle);

            //Cumuler le cout de l'arc au cout total
            coutCycle += coutsCycle[sommetCycle][sommetCycleSuivant];
        }

        /* 2- Calcul de la somme des couts des arcs des affectations */
        for (int s = 0; s < tsp_data.getNbSommets(); s++) {
            //on ne traite que les sommets hors cycle
            if (horsCycle(s,cycle)) {
                coutAffectations += coutsAffectation[s][affectation[s]];
            }
        }

        coutSolution = coutCycle + coutAffectations;
        return coutSolution;
    }
}
